package stu.day39_day.day39;

public class hw2 {
    public int uniquePaths(int m, int n) {
        int[][] arr = new int[m][n];
        arr[0][1] = 1;
        arr[1][0] = 1;
        for(int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                arr[i][j] = dfs(i-1,j,arr)+dfs(i,j-1,arr);
            }
        }

        return arr[m-1][n-1];



    }




    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp =new int[m][n];

        dp[0][0] = 1;
        for(int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if(obstacleGrid[i][j]==0) {
                    if(i!=0||j!=0) {
                        dp[i][j] = dfs(i - 1, j, dp) + dfs(i, j - 1, dp);
                    }
                }else {
                    dp[i][j] = 0;
                }
            }
        }

        return dp[m-1][n-1];

    }
    public int dfs(int i,int j,int[][] arr){
        if(i<0||i>=arr.length||j<0||j>=arr[0].length){
            return 0;
        }
        return arr[i][j];
    }

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

        dp[0][0] = grid[0][0];
        for(int i=1;i<m;i++){
            dp[i][0] = dp[i-1][0]+grid[i][0];
        }
        for(int j=1;j<n;j++){
            dp[0][j] += dp[0][j-1]+grid[0][j];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=grid[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }

        return dp[m-1][n-1];

    }




}
